Récurrence double - Grand Oral

Le principe de récurrence double s'énonce comme suit.

Soit  `P_n` une propriété dépendant de l'entier naturel `n` . Supposons que :

• il existe un entier  `n_0` tel que  `P_{n_0}` et `P_{n_0+1}`   soient vraies (initialisation) ;
  
• pour tout entier \(n \geqslant n_0\) , si  `P_n` et  `P_{n+1}`  sont vraies, alors  `P_{n+2}` est vraie (hérédité) .
  

Alors,   `P_n` est vraie pour tout entier naturel   \(n \geqslant n_0\) .

Exercice

On considère la suite \(\left(F_n\right)\)  (dite de Fibonacci) définie par :  \(F_0=0, F_1=1\)  et, pour tout entier naturel `n` , `F_{n+2}=F_{n+1}+F_{n}` .

1. Calculer \(F_2\) ,  \(F_3\) ,..., \(F_{10}\) .
2. a. Développer \(\left(\dfrac{1+\sqrt{5}}{2}\right)^{2}\)  et \(\left(\dfrac{1-\sqrt{5}}{2}\right)^{2}\) .
    b. Démontrer que \(\forall n\in\mathbb{N},\)   \(F_{n}=\dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1+\sqrt{5}}{2}\right)^{n}-\left(\dfrac{1-\sqrt{5}}{2}\right)^{n}\right)\) .